/*
  This file is a part of hashutils package.
  (c) 2004 Zeljko Vrba <zvrba@globalnet.hr>

  Permission is hereby granted, free of charge, to any person obtaining
  a copy of this software and associated documentation files (the
  "Software"), to deal in the Software without restriction, including
  without limitation the rights to use, copy, modify, merge, publish,
  distribute, sublicense, and/or sell copies of the Software, and to
  permit persons to whom the Software is furnished to do so, subject to
  the following conditions:

  The above copyright notice and this permission notice shall be
  included in all copies or substantial portions of the Software.

  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <sfio.h>
#include <cdt.h>
#include <mycrypt.h>
#include "cdt_bblock.h"
#include "main.h"

#define	DEFAULT_BLOCK_LEN	8

static char rcsid[] = "$Id: bcomm.c 2 2007-03-29 14:43:55Z zeljko.vrba $";
const char *Main_argv0;

static unsigned int
	off_a[2] = { 0, -1U },
	off_b[2] = { 0, -1U },
	block_len = DEFAULT_BLOCK_LEN,
	method = 0;

static unsigned char *f_cont[2];



/******************************************************************************
 * Helper routines.
 *****************************************************************************/

/**
   Read the file into memory. This routine itself does the allocation.
   
   @param	f		File pointer.
   @param	data	Where to store the result of allocation.
   @param	size	Where to store the file size.
*/
static void read_file(Sfio_t *f, unsigned char **data, unsigned int *size)
{
	Sfoff_t sz = sfsize(f);

	if(sz < 0) {
		sfprintf(sfstderr, "FATAL: can't determine file size.\n");
		exit(1);
	}

	*size = sz;
	if(!(*data = vmalloc(BBlock_vmpool, *size))) {
		sfprintf(sfstderr, "FATAL: memory exhausted. Exiting.\n");
		exit(1);
	}
	if(sfread(f, *data, *size) < *size) {
		sfprintf(sfstderr, "ERROR: can't read file: %s\n", strerror(errno));
		exit(1);
	}
}

static unsigned compare_range(
	unsigned char *m1, unsigned char *e1,
	unsigned char *m2, unsigned char *e2)
{
	unsigned int count;

	for(count = 0; (*m1 == *m2) && (m1 < e1) && (m2 < e2); m1++, m2++, count++)
		;
	return count;
}



/******************************************************************************
 * Method 1.
 *****************************************************************************/
static void method1(Dt_t *set1, struct bblock_iterator *it2)
{
	char *h;
	struct bblock_offset *offlist;
	struct bblock_head *head;

	while((h = BBLOCK_NEXT(it2))) {
		if(!(head = dtmatch(set1, h))) continue;
		if(!(offlist = head->offlist)) {
			sfprintf(sfstderr, "INTERNAL ERROR: offset list is NULL.\n");
			abort();
		}
		for(; offlist; offlist = offlist->next) {
			unsigned int mlen = compare_range(
				f_cont[0] + offlist->off, f_cont[0] + off_a[1],
				f_cont[1] + it2->current, f_cont[1] + off_b[1]);
			sfprintf(sfstdout, "%u,%u,%u\n", offlist->off, it2->current, mlen);
		}
	}
}



/******************************************************************************
 * Method 2.
 *****************************************************************************/

/** Structure representing the block match in two files. */
struct match {
	Dtlink_t _l;				/* link */
	unsigned long off[2];		/* offset in each file */
	unsigned int len;			/* match length */
};

/**
   match structs are compared by off[0]. Calculate it the correct way, not
   just subtracting key1 - key2 (it might overflow).
*/
static int match_compare(Dt_t *_0, Void_t *key1, Void_t *key2, Dtdisc_t *_1)
{
	unsigned long x = *(unsigned long*)key1, y = *(unsigned long*)key2;
	return (x > y) - (x < y);
}

static Dtdisc_t Cdt_MatchDiscipline = {
	offsetof(struct match, off), /* key */
	sizeof(unsigned long),		/* key size */
	NULL,						/* makef */
	NULL,						/* freef */
	match_compare,				/* comparison function */
	NULL,						/* hashf */
	NULL,						/* memoryf */
	NULL						/* eventf */
};

static struct match *newmatch(
	unsigned long off1, unsigned long off2,
	unsigned int len)
{
	struct match *m = vmalloc(BBlock_vmpool, sizeof(struct match));
	
	if(!m) {
		sfprintf(sfstderr, "FATAL: memory exhausted. Exiting.\n");
		exit(1);
	}
	m->off[0] = off1; m->off[1] = off2; m->len = len;
	return m;
}

static void method2(Dt_t *set1, struct bblock_iterator *it2)
{
	char *h;
	struct match m;
	Dt_t *matches;

	memset(&m, 0, sizeof(m));

	/* create set */
	if(!(matches = dtopen(&Cdt_MatchDiscipline, Dtoset))) {
		sfprintf(sfstderr, "FATAL: memory exhausted. Exiting.\n");
		exit(1);
	}

	while((h = BBLOCK_NEXT(it2))) {
		struct bblock_head *head;
		struct bblock_offset *offlist;
		
		if(!(head = dtmatch(set1, h))) continue;
		if(!(offlist = head->offlist)) {
			sfprintf(sfstderr, "INTERNAL ERROR: offset list is NULL.\n");
			abort();
		}

		for(; offlist; offlist = offlist->next) {
			unsigned int mlen;
			struct match *p;

			/*
			  check if we are about to compare two suffixes
			  TODO: merge matches!!!
			*/
			m.off[0] = offlist->off;
			if((p = dtprev(matches, &m))) {
				if(((offlist->off - p->off[0]) == (it2->current - p->off[1]))
				&& ((offlist->off - p->off[0]) < p->len)) {
					sfprintf(sfstdout, "FOUND: %u,%u - %u,%u,%u\n",
							 offlist->off, it2->current,
							 p->off[0], p->off[1], p->len);
					continue;
				}
			}

			mlen = compare_range(
				f_cont[0] + offlist->off, f_cont[0] + off_a[1],
				f_cont[1] + it2->current, f_cont[1] + off_b[1]);
			dtinsert(matches, newmatch(offlist->off, it2->current, mlen));

			sfprintf(sfstdout, "%u,%u,%u\n", offlist->off, it2->current, mlen);
		}
	}
}



/******************************************************************************
 * Method 3.
 *****************************************************************************/
static void method3(Dt_t *set1, struct bblock_iterator *it2)
{
	unsigned int i;
	char *h;
	struct match **matches = vmalloc(BBlock_vmpool, off_b[1] * sizeof(struct match*));

	if(!matches) {
		sfprintf(sfstderr, "FATAL: memory exhausted. Exiting.\n");
		exit(1);
	}
	for(i = 0; i < off_b[1]; i++) matches[i] = 0;

	while((h = BBLOCK_NEXT(it2))) {
		struct bblock_head *head;
		struct bblock_offset *offlist;
		
		if(!(head = dtmatch(set1, h))) continue;
		if(!(offlist = head->offlist)) {
			sfprintf(sfstderr, "INTERNAL ERROR: offset list is NULL.\n");
			abort();
		}

		for(; offlist; offlist = offlist->next) {
			unsigned int mlen = compare_range(
				f_cont[0] + offlist->off, f_cont[0] + off_a[1],
				f_cont[1] + it2->current, f_cont[1] + off_b[1]);
			
			if(!matches[it2->current] || mlen > matches[it2->current]->len) {
				struct match *m = newmatch(offlist->off, it2->current, mlen);
				
				matches[it2->current] = m;
				for(i = 1; i < mlen; i++) matches[it2->current + i] = m;
				sfprintf(sfstdout, "%u,%u,%u\n", m->off[0], m->off[1], m->len);
			}
		}
	}
}



/******************************************************************************
 * Implementation of 'main' interface.
 *****************************************************************************/
void Main_usage(const char *message)
{
	sfprintf(sfstderr, "%s\n", message);
	sfprintf(sfstderr, "USAGE: %s [OPTION] HASH FILE1 FILE2\n", Main_argv0);
	sfprintf(sfstderr, "  -aS[,E]        start,end offset in FILE1\n");
	sfprintf(sfstderr, "  -bS[,E]        start,end offset in FILE2\n");
	sfprintf(sfstderr, "  -lL            minimal matching length (DEFAULT: %d)\n", DEFAULT_BLOCK_LEN);
	sfprintf(sfstderr, "  -mMETHOD       matching method\n");
	sfprintf(sfstderr, "\n");
	
	sfprintf(sfstderr, "HASH is one of the following:\n");
	Main_print_hashes();
	exit(1);	
}

int Main_process_option(int argc, char **argv, int *arg)
{
	unsigned int *off = off_b;

	switch(argv[*arg][1]) {
	case 'a':
		off = off_a;
		/* FALLTHROUGH */

	case 'b':
		return
			(sscanf(argv[*arg]+2, "%u,%u", off, off+1) == 2)
			|| (sscanf(argv[*arg]+2, "%u", off) == 1);

	case 'l':
		return sscanf(argv[*arg]+2, "%u", &block_len) == 1;
	
	case 'm':
		if(sscanf(argv[*arg]+2, "%u", &method) != 1) return 0;
		if(method < 1 || method > 3) {
			sfprintf(sfstderr, "ERROR: method must be an integer between 1 and 3\n");
			return 0;
		}
		return 1;
	}
	return 0;
}

/**
   Check that start offset is strictly less than end offset and that the
   interval is at least as large as block length.
*/
#define	OFFSET_CHECK(o)	((o[0] < o[1]) && (o[1] - o[0] >= block_len))

void Main_process_files(const char *fname1, const char *fname2, int halg)
{
	Dt_t *set;
	Sfio_t *file1, *file2;
	char *h;
	unsigned int fsz;
	struct bblock_iterator *it;

	if(!method) {
		sfprintf(sfstderr, "ERROR: -m option is mandatory!\n");
		exit(1);
	}

	/* create Vmlast heap */
	if(!(BBlock_vmpool = vmopen(Vmdcmmap, Vmlast, VM_TRUST))) {
		sfprintf(sfstderr, "FATAL: can't create memory heap, exiting.\n");
		exit(1);
	}

	/* check offsets given on the command line */
	if(!OFFSET_CHECK(off_a) || !OFFSET_CHECK(off_b)) {
		sfprintf(sfstderr, "ERROR: invalid offsets.\n");
		exit(1);
	}

	/* read files into memory */
	file1 = Main_file_open(fname1);
	file2 = Main_file_open(fname2);

	if((file1 == sfstdin) || (file2 == sfstdin)) {
		sfprintf(sfstderr, "FATAL: input can't be from stdin.\n");
		exit(1);
	}

	read_file(file1, f_cont, &fsz);
	if(fsz < off_a[1]) off_a[1] = fsz;
	
	read_file(file2, f_cont+1, off_b+1);
	if(fsz < off_b[1]) off_b[1] = fsz;

	sfclose(file1);
	sfclose(file2);


	/* create the set and store the first file into it */
	Cdt_BBlockDiscipline.size = hash_descriptor[halg].hashsize;
	if(!(set = dtopen(&Cdt_BBlockDiscipline, Dtset))) {
		sfprintf(sfstderr, "FATAL: memory exhausted. Exiting.\n");
		exit(1);
	}

	it = BBlock_mem_begin(f_cont[0], off_a[0], off_a[1], block_len, halg);
	while((h = BBLOCK_NEXT(it))) BBlock_insert(set, h, it->current);

	/* now invoke the appropriate method */
	it = BBlock_mem_begin(f_cont[1], off_b[0], off_b[1], block_len, halg);
	switch(method) {
	case 1:
		method1(set, it);
		break;

	case 2:
		method2(set, it);
		break;

	case 3:
		method3(set, it);
		break;

	default:
		sfprintf(sfstderr, "INTERNAL ERROR: unallowed method %u\n", method);
		abort();
	}
}
